class Gift {
public:
/*
 // 计数统计
    int getValue(vector<int> gifts, int n) {
        int cnt[100001] = {0};
        for(int i = 0; i < gifts.size(); ++i)
            ++cnt[gifts[i]];
        for(int i = 0; i < gifts.size(); ++i){
            if(cnt[gifts[i]] > n/2)
                return gifts[i];
        }
        return 0;
    }
*/
 // 根据数组特点 时间复杂度O(n)
    // 检验有没有次数超过一半的数字
    bool Check(vector<int> v, int n, int num){
        int times = 0;
        for(int i = 0; i < n; ++i){
            if(num == v[i])
                ++times;
        }  
        return times > (n >> 1);
    }
    int getValue(vector<int> gifts, int n){
        int num = gifts[0];  // 数字
        int times = 0;   // 次数
        for(int i = 0; i < n; ++i){
            if(times == 0){
                num = gifts[i];
                times = 1;
            }
            else if(num == gifts[i])
                ++times;
            else
                --times;
        }
        if(!Check(gifts, n, num))  //不满足条件
            return 0;
        
        return num;
    }
};